//
// Created by Jisam on 2024/7/14.
//
#include <bits/stdc++.h>
#define PSI pair<string,int>
#define PII pair<int,int>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define ll long long

using namespace std;

const int N = 1e5 + 5;
int ans;

void backTrack(int row, int n, int cols, int diag1, int diag2, vector<int>& queens, vector<vector<int>>& result) {
    if(queens.size() >= 3){
        return;
    }

    if (row == n) { // 如果已经放置完所有皇后，则找到了一个解
        result.push_back(queens);
        return;
    }

    int availablePositions = ((1 << n) - 1) & (~(cols | diag1 | diag2)); // 可用的位置是当前列、左上对角线和右上对角线均没有皇后的位置
    while (availablePositions != 0) { // 对所有可用的位置进行遍历
        int position = availablePositions & (-availablePositions); // 获取最低位的1，即可放置皇后的位置
        availablePositions &= (availablePositions - 1); // 清除最低位的1，将该位置标记为已使用

        int col_num = __builtin_ctz(position); // 获取位置的列数

        queens[row] = col_num; // 将皇后放置在该位置
        // 更新列、对角线的状态，并继续递归放置下一行的皇后
        backTrack(row + 1, n, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1, queens, result);
    }
}

vector<vector<int>> solveNQueens(int n) {
    vector<vector<int>> result;
    vector<int> queens(n, 0); // 用于存储每行皇后所在的列数

    backTrack(0, n, 0, 0, 0, queens, result); // 从第0行开始放置皇后

    return result;
}

int main() {
    int n;
    cin >> n; // 输入棋盘的大小

    vector<vector<int>> solutions = solveNQueens(n); // 求解所有解
    int count = solutions.size(); // 解的总个数

    // 输出前三个解
    for (int i = 0; i < min(3, count); i++) {
        for (int j = 0; j < n; j++) {
            cout << solutions[i][j] + 1 << " "; // 将列数加1输出，表示皇后所在的列
        }
        cout << endl;
    }

    cout << count << endl; // 输出解的总个数

    return 0;
}